The present invention is directed to a method, system and apparatus for performing a halftoning process with respect to image data. In particular, the present invention is directed to methods and systems for performing halftoning on image data for output to a display device.
Imaging devices, such as printers and displays, are typically capable of outputting a certain number of colors at each location output. This capability is referred to as the device's “bit-depth.”
Halftoning of image data is required whenever the output image bit-depth is smaller than the input image data bit-depth. This situation occurs most often in devices such as printers or multifunction devices (MFDs) where there are most commonly only two possibilities at each physical location: leave paper unprinted or put toner/ink at location. In addition to MFDs, halftoning is also often needed for outputting image data to computer displays, such as cathode ray tube (CRT) or liquid crystal display (LCD) monitors.
As an example, consider a MFD that includes a scanner portion and a printer portion. Some such devices can include a monitor portion for previewing images scanned via the scanner portion or otherwise received from another source such as a computer network connection. The scanner can typically create image scans in various reproductive formats, such as 24 bit RGB, 32 bit CMYK, 8 bit gray, or binary CMYK. The image with multiple levels of gray or color (i.e., a continuous tone image) is rendered from the scanner to the printer in a halftoning process.
To perform optimally, a MFD may require that the scanner generate binary, monochrome, or color data. However, the binary data must include sufficient compensation to enable the printer portion to meet standard copy quality requirements. This function is usually accomplished by building in static color tables or transfer functions for the scanner portion and the printer portion and further modifying the scanned image. Accordingly, autonomous scanning stations may have standard color profiles that a user may select. In addition, vendors may provide software and/or hardware solutions that serve to calibrate the colors and/or gray shading of a scanned image.
Most halftoning methods are spatially based, i.e., they use the human visual system spatial averaging properties that average over a neighborhood of bi-level pixels to provide a sensation of intermediate color level. Typical steps in a rendering process include converting the resolution or DPI (dots per inch) of the digital image to the desired display or print resolution, converting the digital image color space to the display device colorant color space (e.g. RGB to CMYK), and converting the display device colorants to display device dot data. The architecture of the processing element or elements performing this task should produce a high quality transformation that is pleasing to the eye from the digital image to display device while providing high performance at the lowest cost and size possible. Therefore, the algorithms used for each step must be carefully selected and implemented with these goals in mind.
A traditional method of converting the display device colorants to display device dot data is known as error diffusion. This process has been known for many years and was originally derived by Floyd and Steinberg. A description of this process is provided herein for illustrative purposes with reference to FIG. 1. The squares 140 represent the pixels of an input image. The shaded squares 160 represent pixels that have not been processed as yet. Square 110 is an example of a pixel determined to require placement of a dot; square 120 is an example of a pixel determined not require placement of a dot. Square 130 represents the pixel under current examination by the error diffusion process.
As the process progresses, a pixel value associated with the current pixel is compared against a threshold value to determine the output corresponding to the current pixel (dot placement or no dot placement). For instance, assume that the pixel value is in the range of 0-255 as would often be the case for a 256 color gray-scale input image (assuming 0 represents black and 255 represents white), if a threshold value is 127 for a particular pixel, an output of dot placement would occur if the pixel value were 127 or less, and an output of no dot placement would occur if the pixel value were above 127. Next an error associated with this pixel is calculated; the error is calculated by subtracting the particular pixel value from the pixel value associated with the output. To continue with the example, the pixel value would be the error (pixel value −0) if the output were dot placement and would be the pixel value minus 255 if the output were no dot placement. The error is then distributed to neighboring pixel below the current pixel and in front of the current pixel in the direction of error diffusion processing. The neighborhood of pixels to which error is diffused varies depending upon implementation. A common neighborhood of pixels includes the pixel immediately in front of the current pixel (e.g., square 170) and the three pixels immediately below the current pixel (e.g., squares 182, 184 and 186). The calculated error is diffused to the neighborhood according to a weighting scheme that attributes a portion of the error to each pixel in the neighborhood; a typical weighing distributes 7/16 of the error to the pixel in front (e.g., square 170), 3/16 to the pixel below and behind (e.g., square 182), 5/16 to the pixel immediately below (e.g., square 184) and 1/16 to the pixel below and in front (e.g., square 186).
The present invention provides for systems and methods for improving performance of the error diffusion with respect to an input digital image. The present invention provides such image processing that can meet certain size and performance goals as well as provide the necessary functionality to transform a digital image to printer ink dots or display pixels. Such a print processing can produce a high quality, aesthetically pleasing, transformation from digital image data to printer ink dot data or display pixels while providing high performance in a compact, low cost solution.